/*
 * BST.java
 *
 * Created on February 20, 2007, 4:32 PM
 */

// Original code found in "Data Abstraction & Problem Soving with Java"
// 2005., Carrano, F., Prichard, J.;

import java.io.*;
import java.util.*;

public class BST<T extends KeyedItem<KT>, KT extends Comparable<? super KT>>
    extends BinaryTreeBasis<T>
{
    //*************************************************************
    public BST()
    {
    }

    /** Creates a new instance of BST */
    //*************************************************************
    public BST(T rootItem)//Done
    {
        super(rootItem);
    }
	//*************************************************************
    public void setRootItem(T newItem)//?
        throws UnsupportedOperationException
    {
        throw new UnsupportedOperationException();
    }
	//*************************************************************
    public void insert(T newItem)//done
    {
        root = insertItem(root, newItem);
    }
	//*************************************************************
    public T retrieve(KT searchKey)//done
    {
        return retrieveItem(root, searchKey);
    }
	//*************************************************************
    public void delete(KT searchKey) throws TreeException//done
    {
        root = deleteItem(root, searchKey);
    }
	//*************************************************************
    public void delete(T item) throws TreeException//done
    {
        root = deleteItem(root, item.getKey());
    }
	//*************************************************************
    protected TreeNode<T> insertItem(TreeNode<T> tNode, T newItem)//done
    {
        TreeNode<T> newSubtree;
        if (tNode == null)
        {
            tNode = new TreeNode<T>(newItem, null, null);
            return tNode;
        }

        T nodeItem = tNode.getItem();

        if (newItem.getKey().compareTo(nodeItem.getKey()) < 0)
        {
            newSubtree = insertItem(tNode.getLeft(), newItem);
            tNode.setLeft(newSubtree);
            return tNode;
        }
        else
        {
            newSubtree = insertItem(tNode.getRight(), newItem);
            tNode.setRight(newSubtree);
            return tNode;
        }
    }
	//*************************************************************
    protected T retrieveItem(TreeNode<T> tNode, KT searchKey)//done
    {
        T treeItem;
        if (tNode == null)
        {
            treeItem = null;
        }
        else
        {
            T nodeItem = tNode.getItem();
            if (searchKey.compareTo(nodeItem.getKey()) == 0)
            {
                treeItem = tNode.getItem();
            }
            else if (searchKey.compareTo(nodeItem.getKey()) < 0)
            {
                treeItem = retrieveItem(tNode.getLeft(), searchKey);
            }
            else
            {
                treeItem = retrieveItem(tNode.getRight(), searchKey);
            }
        }
        return treeItem;

    } // end retrieveItem
	//*************************************************************
    protected TreeNode<T> deleteItem(TreeNode<T> tNode, KT searchKey)//done
    {

        TreeNode<T> newSubtree;
        if (tNode == null)
        {
            throw new TreeException("TreeException: Item not Found");
        }
        else
        {
            T nodeItem = tNode.getItem();
            if (searchKey.compareTo(nodeItem.getKey()) == 0)
            {
                tNode = deleteNode(tNode);
            }
            else if (searchKey.compareTo(nodeItem.getKey()) < 0)
            {
                newSubtree = deleteItem(tNode.getLeft(), searchKey);
                tNode.setLeft(newSubtree);
            }
            else
            {
                newSubtree = deleteItem(tNode.getRight(), searchKey);
                tNode.setRight(newSubtree);
            }
        }

        return tNode;
    }
	//*************************************************************
    protected TreeNode<T> deleteNode(TreeNode<T> tNode)//done
    {

        T replacementItem;

        // test for a leaf
        if ( (tNode.getLeft() == null) && (tNode.getRight() == null) )
        {
            return null;
        }

        // test for no left child
        else if (tNode.getLeft() == null)
        {
            return tNode.getRight();
        }

        // test for no right child
        else if (tNode.getRight() == null)
        {
            return tNode.getLeft();
        }

        else
        {
            replacementItem = findLeftmost(tNode.getRight());
            tNode.setItem(replacementItem);
            tNode.setRight(deleteLeftmost(tNode.getRight()));
            return tNode;
        }
    }
	//*************************************************************
    protected T findLeftmost(TreeNode<T> tNode)//done
    {
        if (tNode.getLeft() == null)
        {
            return tNode.getItem();
        }
        else
        {
            return findLeftmost(tNode.getLeft());
        }
    }
	//*************************************************************
    protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode)//done
    {
        if (tNode.getLeft() == null)
        {
            return tNode.getRight();
        }

        else
        {
            tNode.setLeft(deleteLeftmost(tNode.getLeft()));
            return tNode;
        }
    }
    //*************************************************************
    public void SaveToFile(TreeNode<T> root, String inputFileName) throws IOException//done
    {
		PrintWriter out = new PrintWriter(new FileWriter(inputFileName));

		try
		{
		Save(root, out);
		}
		catch(IOException e)
		{
		}

		out.close();
	}

	//************************************************************
	private void Save(TreeNode<T> root,
						PrintWriter out) throws IOException//done
	{
		if (root != null)
		{
			out.println(root.getItem().toString());
			Save(root.getLeft(), out);
			Save(root.getRight(), out);
		}
	}
	

	//***********************************************************
	public void InOrder(TreeNode<T> root, Vector myVector)
	{
		if (root != null)
		{
			InOrder(root.getLeft(), myVector);
			myVector.add(root.getItem());
			InOrder(root.getRight(), myVector);
		}
	}

	//***********************************************************
	public void PreOrder(TreeNode<T> root, Vector myVector)
	{
		if (root != null)
		{
			myVector.add(root.getItem());
			PreOrder(root.getLeft(), myVector);
			PreOrder(root.getRight(), myVector);
		}
	}

	//***********************************************************
	public void PostOrder(TreeNode<T> root, Vector myVector)
	{
		if (root != null)
		{
			PostOrder(root.getLeft(), myVector);
			PostOrder(root.getRight(), myVector);
			myVector.add(root.getItem());
		}
	}

	//**********************************************************

	public static int CalcHeight (TreeNode root)
	{
		if (root == null)
		{
			return 0;
		}
		else
		{
			int leftHeight = CalcHeight(root.getLeft());
			int rightHeight = CalcHeight(root.getRight());
			if(leftHeight > rightHeight)
				return leftHeight + 1;
			else
				return rightHeight + 1;
		}
	}
        
        //**********************************************************
        
        public void BSTmakeEmpty()
        {
            makeEmpty();
        }
}